package Algorithm.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Desc:   无重复字符的最长子串
 * @author: cww
 * @DateTime: 2020/3/27 14:20
 */

public class LengthOfLongestSubstring {

    public static void main(String[] args) {
        System.out.print(lengthOfLongestSubstring_2("lwpo-ef0doc"));
    }

    /**
     * Set 滑块
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring_1(String s) {
        Set<Character> set = new HashSet<>();
        int n = s.length();
        int max = 0, i = 0, j = 0;
        while(i < n && j < n) {
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                max = Math.max(max, j-i);
            } else {
                // 如果出现重复的，删除 i 开始的地方，删除后继续检查当前的 j 位置和 i++ 后的位置
                set.remove(i++);
            }
        }
        return max;
    }
    /**
     * 优化 Set 滑块
     * 上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。
     * 我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
     * 也就是说，如果 s[j] 在 [i, j)[i,j) 范围内有与 j'重复的字符，我们不需要逐渐增加 i。
     * 我们可以直接跳过 [i，j']范围内的所有元素，并将 i 变为 j′+1。
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring_2(String s) {
        int n = s.length();
        int max = 0, i=0;
        Map<Character, Integer> map = new HashMap<>();
        for(int j =0; j < n; j++) {
            if(map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            max = Math.max(max, j-i + 1);
            // j + 1 表示当前字符的位置，当出现相同的字符时，直接将该字符设给 i
            map.put(s.charAt(j), j + 1);
        }
        return max;

    }
}
